#include <iostream>
#include <vector>
#include <random>

using namespace std;

class Solution
{
    void dfs(vector<int> &arr, int target, int &md)
    {
        if (target == 0)
        {
            mid = md;
            return;
        }

        for (int i = 0; i < arr.size(); i++)
        {
            int tg = target - arr[i];
            if (!used[i] && tg >= 0)
            {
                used[i] = true;
                dfs(arr, tg, ++md);
                used[i] = false;
                --md;
            }
            else
            {
                mid = 0x3f3f3f3f;
            }
        }
    }

    int ret = 0x3f3f3f3f;
    int mid = 1;
    vector<bool> used;

public:
    int Mincount(vector<int> &arr, const int &target)
    {
        int n = arr.size();
        used.assign(n, 0);
        for (int i = 0; i < n; i++)
        {
            int tg = target - arr[i];
            used[i] = true;
            int md = 1;
            dfs(arr, tg, md);
            ret = min(ret, mid);

            used[i] = false;
        }
        return ret;
    }
};

int main()
{
    unsigned int seed = 202111672313;
    default_random_engine rng(seed);
    uniform_int_distribution<int> dist(1, 100); // 生成1至100之间的随机数

    // 生成测试数据
    vector<int> nums;
    for (int i = 0; i < 10; ++i)
    { // 生成10个随机数
        nums.push_back(dist(rng));
    }
    int target = dist(rng); // 生成目标值

    cout << "Generated numbers:";
    for (int num : nums)
    {
        cout << " " << num;
    }
    cout << endl
         << "Target sum: " << target << endl;
    cout << "Subsets with sum equal to target:" << endl;

    Solution s;
    cout << s.Mincount(nums, target) << endl;

    return 0;
}